public class ReverseWords {
    public String reverseWords(String s) {
        //先整体翻转，再单词内部翻转
        int left = 0;
        int right = s.length() - 1;
        //处理最前面和最后面的空格
        while (s.charAt(left) == ' ') {
            left++;
        }
        while (s.charAt(right) == ' ') {
            right--;
        }

        StringBuilder sb = new StringBuilder();
        int spaceCnt = 0;  //空格的次数
        for (int i = right; i >= left; i--) {
            char ch = s.charAt(i);
            if (ch == ' ') {
                spaceCnt++;
            } else {
                spaceCnt = 0;
            }
            if (ch != ' ' || spaceCnt == 1) {
                sb.append(ch);
            }
        }
        left = 0;  //因为接下来要遍历的是sb字符串，所以left和right都要更新
        int front = left; //表示单词的第一个字母
        right = sb.length() - 1;
        while (left <= right) {
            while (left <= right && sb.charAt(left) != ' ') {
                left++;
            }
            reverse(sb, front ,left - 1);
            left++;
            front = left;  //更新front坐标
        }
        return sb.toString();
    }
    //反转
    public void reverse(StringBuilder sb, int i, int j) {
        while (i <= j) {
            char ch = sb.charAt(i);
            sb.setCharAt(i++, sb.charAt(j));
            sb.setCharAt(j--, ch);
        }
    }
}
